// 拓扑排序 - 找做事情的顺序
// 1.找出图中入度为 0 的点，然后输出
// 2.删除与该点连接的边
// 3.重复 1，2 操作，直到图中没有点或者没有入度为 0 （有环）的点为止
// 4.重要应用 - 判断有向图中是否有环
// 5.借助队列，进行一次 bfs
//     1).入度为 0，加入队列
//     2).当队列不为空：
//         1).拿出队头元素
//         2).删除与该元素相连的边
//         3).判断与删除边相连的点，是否入度为 0，如果为 0，加入到队列中

// 例题 3：
// 现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
// 定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
// 请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 "" 。
// 若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
//
//        字符串 s 字典顺序小于 字符串 t 有两种情况：
//
//        在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
//        如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
//
//
//        示例 1：
//
//        输入：words = ["wrt","wrf","er","ett","rftt"]
//        输出："wertf"
//        示例 2：
//
//        输入：words = ["z","x"]
//        输出："zx"
//        示例 3：
//
//        输入：words = ["z","x","z"]
//        输出：""
//        解释：不存在合法字母顺序，因此返回 ""。
//
//
//        提示：
//
//        1 <= words.length <= 100
//        1 <= words[i].length <= 100
//        words[i] 仅由小写英文字母组成

// 解题思路：
// 建图：统计所有字母的入度，以及邻接表
// 统计入度和建立邻接表的时候，注意不要统计冗余信息
// 可以使用双指针的方法，统计邻接表
// 实现拓扑排序：
// 借助队列，进行一次 bfs
//     1).入度为 0，加入队列
//     2).当队列不为空：
//         1).拿出队头元素，并添加到结果数组中
//         2).删除与该元素相连的边
//         3).判断与删除边相连的点，是否入度为 0，如果为 0，加入到队列中
// 如果仍然存在元素的入度不为 0，返回空数组，否则返回结果数组;

import java.util.*;

public class AlienOrder {
    public String alienOrder(String[] words) {
        // 1.准备工作
        Map<Character, Integer> hash = new HashMap<>();// 统计入度
        int n = words.length;
        // 统计都有哪些字母
        for (String word : words) {
            char[] chArr = word.toCharArray();
            for (char ch : chArr) hash.put(ch, 0);
        }
        Map<Character, Set<Character>> edges = new HashMap<>();// 统计邻接表
        // 2. 建图
        for(int i = 0; i < n; i++){
            char[] arr1 = words[i].toCharArray();
            int len1 = arr1.length;
            for(int j = i + 1; j < n; j++){
                char[] arr2 = words[j].toCharArray();
                int len2 = arr2.length;
                int len = Math.min(len1, len2);
                boolean flag = false;
                for(int k = 0; k < len; k++){
                    if(arr1[k] != arr2[k]){
                        flag = true;
                        if(!edges.containsKey(arr1[k])){
                            edges.put(arr1[k], new HashSet<>());
                        }
                        if(!edges.get(arr1[k]).contains(arr2[k])){
                            edges.get(arr1[k]).add(arr2[k]);
                            hash.put(arr2[k], hash.get(arr2[k]) + 1);
                        }
                        break;
                    }
                }
                if(!flag && len1 > len2) return "";
            }
        }
        // 3. 拓扑排序
        Queue<Character> queue = new LinkedList<>();
        for(char ch : hash.keySet()){
            if(hash.get(ch) == 0) queue.offer(ch);
        }
        StringBuilder ret = new StringBuilder();
        while(!queue.isEmpty()){
            char t = queue.poll();
            ret.append(t);
            for(char ch : edges.getOrDefault(t, new HashSet<>())){
                hash.put(ch, hash.get(ch) - 1);
                if(hash.get(ch) == 0) queue.offer(ch);
            }
        }
        // 4. 返回结果
        for(char ch : hash.keySet()){
            if(hash.get(ch) != 0) return "";
        }
        return ret.toString();
    }
}
